package com.njupt.DynamicProgramming;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/2/5 20:14
 * @Description: 1049. 最后一块石头的重量 II
 * 可以建模成划分成重量相近的两部分weight1和weight2.所以可以定义背包容量为总容量的一半
 * @Version: 1.0
 */


public class LastStoneWeightII_1049 {

    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int i = 0; i < stones.length; i++) {
            sum += stones[i];
        }
        int target = sum / 2;
        int[] dp = new int[target+1];

        for (int i = 0; i < stones.length; i++) {
            for (int j = target; j >= stones[i] ; j--) {
                dp[j] = Math.max(dp[j],dp[j-stones[i]] + stones[i]);
            }
        }
        return sum - dp[target] -dp[target];

    }

    public static void main(String[] args) {
        int[] stones = {31,26,33,21,40};
        LastStoneWeightII_1049 test = new LastStoneWeightII_1049();
        System.out.println(test.lastStoneWeightII(stones));
    }
}
